Chihik's Blog

An Ac a day, keeps the doctor away!

CF17E Palisection

发布于 2020-10-14 | 分类于 回文自动机 | 4分钟 | 604字数

答案为所有的回文串组合-不相交的回文串组合。

记 cntcnt 为回文串个数 ， 可以通过计算每个节点的回文串数量求得。

不相交的回文组合也比较好求，先算出以 ii 为左端点和右端点的回文串数量 L[i]L[i] , R[i]R[i]。

阅读全文 »

UVA1218 Perfect Service

发布于 2020-10-14 | 分类于 树形dp | 4分钟 | 584字数

一道很不错的树形dp。

令 dp[u][f]dp[u][f] 为以uu为根的子树。

f=0f=0，表示uu为服务器，那么uu的儿子和父亲既可以是服务器，也可以不是。

阅读全文 »

CF767C Garland

发布于 2020-10-14 | 分类于 树形dp | 2分钟 | 321字数

首先可以确定的是，如果点权和不为3的倍数，一定不存在合法方案。

记所有点权和为sumsum。

容易想到，令 dp[u]dp[u] 表示以 uu 为根的子树的点权和 ， 则有转移：

阅读全文 »

SP9934 ALICE - Alice and Bob

发布于 2020-09-28 | 分类于 博弈论 | 3分钟 | 477字数

这道题的状态挺难设计的。。。

令 ss 为石子的总数，那么操作次数最多为 s+(n−1)s+(n-1)

如果石子数量全不为一，那么先手必胜的条件为 s+(n−1)s+(n-1) 为奇数，因为他一定可以保证操作 s+(n−1)s+(n-1) 次。

阅读全文 »

UVA1500 Alice and Bob

发布于 2020-09-28 | 分类于 博弈论 | 3分钟 | 477字数

这道题的状态挺难设计的。。。

令 ss 为石子的总数，那么操作次数最多为 s+(n−1)s+(n-1)

如果石子数量全不为一，那么先手必胜的条件为 s+(n−1)s+(n-1) 为奇数，因为他一定可以保证操作 s+(n−1)s+(n-1) 次。

阅读全文 »

P4056 [JSOI2009]火星藏宝图

发布于 2020-09-23 | 分类于 斜率优化 | 3分钟 | 472字数

首先有一个非常 naive 的 O(n2)\mathcal{O(n^2)} dp。

令 dpidp_i 表示到第 ii 座岛的最大收益，那么有：

dpi=max⁡1≤j≤n,j=i,xj≤xi,yj≤yi{dpj−(xi−xj)2−(yi−yj)2}+vidp_i=\max_{1\le j \le n, j \not= i ,x_j \le x_i ,y_j \le y_i }\{dp_j-(x_i-x_j)^2-(y_i-y_j)^2\}+v_i

阅读全文 »
0%